# 调用函数时计算机会在栈中为函数分配一块内存
# 递归函数使用到了调用栈，递归可能使得程序更容易理解，但运行效率可能不及循环
# 递归深度很深的话可能会造成调用栈很长，也会占用较大的内存

# 下面是一个计算阶乘的递归函数
def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)


# 求解第n个斐波那契数的方法
def get_fibonacci(n: int) -> int:                # O(2^n)
    """

    :rtype: int
    """
    if n <= 0:
        return 0
    if n == 1:
        return 1
    return get_fibonacci(n - 2) + get_fibonacci(n - 1)


# 使用备忘录法优化求解第n个斐波那契数
def get_fibonacci_memo(n: int, memo: dict) -> int:       # O(n)
    if n in memo.keys():
        return memo[n]
    if n <= 0:
        return 0
    if n == 1:
        return 1
    result = get_fibonacci_memo(n - 2, memo) + get_fibonacci_memo(n - 1, memo)
    memo[n] = result
    return result
